interface LinkedListItem<T> {
    data: T;
    next: LinkedListItem<T> | null;
}

export default class LinkedList<T> {
    private head: LinkedListItem<T> | null = null;

    public append(item: T) {
        const newNode = {
            data: item,
            next: null,
        };

        if (!!this.head) {
            let node = this.head;
            while (!!node.next) {
                node = node.next;
            }
            node.next = newNode;
        } else {
            this.head = newNode;
        }
    }

    public insertBefore(insertedItem: T, targetItem: T) {
        const res = this.findNodeRelative(targetItem);
        if (!!res) {
            const newNode: LinkedListItem<T> = {
                data: insertedItem,
                next: null,
            };
            if (!!res.prev) {
                res.prev.next = newNode;
            } else {
                this.head = newNode;
            }
            newNode.next = res.node;
            return true;
        } else {
            return false;
        }
    }

    public insertAfter(insertedItem: T, targetItem: T) {
        const res = this.findNodeRelative(targetItem);
        if (!!res) {
            const newNode: LinkedListItem<T> = {
                data: insertedItem,
                next: null,
            };
            if (!!res.node.next) {
                newNode.next = res.node.next;
            }
            res.node.next = newNode;
            return true;
        } else {
            return false;
        }
    }

    public remove(item: T) {
        const res = this.findNodeRelative(item);
        if (!!res) {
            if (!!res.prev) {
                // delete non-first
                res.prev.next = res.node.next;
            } else {
                // delete first
                this.head = res.node.next;
            }
            res.node.next = null;
        }
    }

    public replace(newItem: T, oldItem: T) {
        const res = this.findNodeRelative(oldItem);
        if (!!res) {
            res.node.data = newItem;
        }
    }

    public includes(item: T) {
        let node = this.head;
        while (!!node) {
            if (node.data !== item) {
                node = node.next;
            } else {
                return true;
            }
        }

        return false;
    }

    public forEach(callback: (item: T) => void, thisArg?: any) {
        let node = this.head;
        while (!!node) {
            callback.call(thisArg, node.data);
            node = node.next;
        }
    }

    private findNodeRelative(item: T) {
        let node = this.head;
        let prev: LinkedListItem<T> | null = null;
        while (!!node) {
            if (node.data !== item) {
                prev = node;
                node = node.next;
            } else {
                return {
                    prev,
                    node,
                };
            }
        }

        return null;
    }
}